package com.lx.algorithm.quickSort;

/**
 * Description: partition
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-09-06 11:28:49
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-09-06     张李鑫                     1.0         1.0 Version
 */
public class QuickSort {

    /**
     * todo:快速随机快排 后续实现
     */

    public static void main(String[] args) {
        int[] arr = {4, 3, 2, 1, 4, 2};
        sort(arr);
        System.out.println(123);
    }

    public static void sort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        process(arr, 0, arr.length - 1);
    }

    private static void process(int[] arr, int L, int R) {
        if (L >= R) {
            return;
        }
        int[] arrays = partition(arr, L, R);
        process(arr, L, arrays[0] - 1);
        process(arr, arrays[1] + 1, R);
    }

    private static int[] partition(int[] arr, int L, int R) {
        if (L > R) { // L...R L>R
            return new int[]{-1, -1};
        }
        if (L == R) {
            return new int[]{L, R};
        }
        int l = L - 1;
        int r = R;
        int index = L;
        while (index < r) {
            if (arr[index] > arr[R]) {
                swap(arr, index, r--);
            } else if (arr[index] == arr[R]) {
                index++;
            } else {
                swap(arr, ++l, index++);
            }
        }
        swap(arr, R, index + 1);
        return new int[]{index, r};
    }


    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
